/*给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
* 子数组大小 至少为2，且
* 子数组元素总和为k的倍数。
* 如果存在，返回true ；否则，返回false 。
* 如果存在一个整数n ，令整数x符合x = n * k ，则称 x 是 k 的一个倍数。
*
* 输入：nums = [23,2,4,6,7], k = 6
* 输出：true
* 解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。
* */

package Leetcode;

import java.util.HashMap;

public class leetcode523 {

    public static void main(String[] args) {

        leetcode523 obj = new leetcode523();
        int[] nums = {1,0};
        int k = 2;
        System.out.println(obj.checkSubarraySum(nums, k));
    }

    public boolean checkSubarraySum(int[] nums, int k){

        //暴力法，超时
//        int len = nums.length;
//        if (len < 2){
//            return false;
//        }
//        int[] sum = new int[len];
//        sum[0] = nums[0];
//        for (int i = 1;i < len;i++){
//            sum[i] = sum[i - 1] + nums[i];
//        }
//        for (int j = 0;j < len;j++){
//            if (sum[j] % k ==0 && j >= 1){
//                return true;
//            }
//        }
//        for (int m = 1;m < len;m++){
//
//            for (int n = 1;n < m;n++){
//
//                if ((sum[m] - sum[n - 1]) % k == 0 && m - n >= 1){
//                    return true;
//                }
//            }
//        }
//        return false;

        //前缀和 + 哈希表
        //若数组[a, b, c]和数组[a, b, c, d, e, f]对k求余后的余数相同，则有
        //a + b + c = x * k + rem
        //a + b + c + d + e + f = y * k + rem
        //则有两数组的差(可得到一个子数组), d + e + f = (x + y) * k, 为k的倍数
        int len = nums.length;
        if (len < 2){
            return false;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int rem = 0;
        for (int i = 0;i < len;i++){

            //求出前缀余数
            rem = (rem + nums[i]) % k;
            if (map.containsKey(rem)){
                if (i - map.get(rem) >= 2) return true;
            }else {
                map.put(rem, i);
            }
        }
        return false;
    }
}
